
/**
 * @author VernHe
 * @date 2021年05月28日 13:31
 */
public class Solution_105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, inorder.length,0, preorder.length);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int i_start, int i_end, int p_start, int p_end) {
        // 递归基
        // 当没有元素的时候
        if (p_start == p_end) {
            return null;
        }
        // 当前根节点
        TreeNode root = new TreeNode(preorder[p_start]);
        int curIndex = 0;
        for (int i = i_start; i < i_end; i++) {
            if (preorder[p_start] == inorder[i]) {
                curIndex = i;
                break;
            }
        }
        // 左边元素个数
        int leftNum = curIndex - i_start;

        root.left = buildTree(preorder,inorder,i_start,curIndex,p_start + 1,p_start + leftNum + 1);
        root.right = buildTree(preorder,inorder,curIndex + 1,i_end,p_start + leftNum + 1,p_end);
        return root;
    }

}
